package cc.rico.algorithm;

/**
 * @Author: Dell
 * @Date: 2018/12/5
 * @Description:插入排序
 * 直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] items = new int[] {23, 22, 5, 6, -5, 90, 43, 90, 1};
        PrintUtil.printArray(items);
        System.out.println("===========================================");

        int[] sortUpItems = sortUp(items);
//        PrintUtil.printArray(sortUpItems);
        System.out.println("===========================================");


        int[] sortDownItems = sortDown(items);
        //PrintUtil.printArray(sortDownItems);
    }

    private static int[] sortUp(int[] items) {
        if(items[0] > items[1]) {
            int temp = items[1];
            items[1] = items[0];
            items[0] = temp;
        }

        for(int i=2; i<items.length; i++) {
            int current = items[i];

            if(items[i-1] <= current) {
                PrintUtil.printArray(items);
                continue;
            }

            if(items[0] >= current) {
                int k = i;
                while (k > 0) {
                    items[k] = items[k-1];
                    k--;
                }

                items[0] = current;
                PrintUtil.printArray(items);
                continue;
            }

            for(int j=i-1; j>0; j--) {
                if(items[j-1]<current && items[j]>current) {
                    int k = i;
                    while (k > j) {
                        items[k] = items[k-1];
                        k--;
                    }

                    items[j] = current;
                    PrintUtil.printArray(items);
                    break;
                }
            }
        }

        return items;
    }

    private static int[] sortDown(int[] items) {
        int[] origin = items.clone();

        int len = items.length;

        if(items[1] > items[0]) {
            int temp = items[0];
            items[0] = items[1];
            items[1] = temp;
        }

        for(int i=2; i<len; i++) {
            int current = items[i];

            if(current <= items[i-1]) {
//                System.out.println("================MAX==================");
//                System.out.print("origin:");
//                PrintUtil.printArray(origin);
                PrintUtil.printArray(items);
                continue;
            }

            if(current >= items[0]) {
                int k = i;
                while (k > 0) {
                    items[k] = items[k-1];
                    k--;
                }

                items[0] = current;
//                System.out.println("================MIN==================");
//                System.out.print("origin:");
//                PrintUtil.printArray(origin);
                PrintUtil.printArray(items);
                continue;
            }

            for(int j=1; j<i; j++) {
                if(items[j]<=current && current <=items[j-1]) {
                    int k = i;
                    while (k > j) {
                        items[k] = items[k-1];
                        k--;
                    }

                    items[j] = current;
//                    System.out.println("================MID==================");
//                    System.out.print("origin:");
//                    PrintUtil.printArray(origin);
                    PrintUtil.printArray(items);
                    break;
                }
            }

//            System.out.println("================ITEM==================");
//            System.out.print("origin:");
//            PrintUtil.printArray(origin);
//            PrintUtil.printArray(items);
        }

        return items;
    }

}
